package leetcode;

import java.util.Arrays;

/**
 * 1234. 替换子串得到平衡字符串    https://leetcode.cn/problems/replace-the-substring-for-balanced-string
 */
public class LeetCode1234 {

    public static int balancedString(String s) {
        int[] chars = new int[s.length()];
        int[] counts = new int[4];
        for (int i = 0; i < s.length(); i++) {
            chars[i] = s.charAt(i) == 'Q' ? 0 : s.charAt(i) == 'W' ? 1 : s.charAt(i) == 'E' ? 2 : 3;
            counts[chars[i]]++;
        }
        int n = s.length();
        int ans = n;
        for (int l = 0, r = 0; l < n; l++) {
            while (!ok(l, r, counts) && r < n) {
                --counts[chars[r++]];
            }
            if (ok(l, r, counts)) {
                ans = Math.min(ans, r - l);
            } else {
                break;
            }
            counts[chars[l]]++;
        }
        return ans;
    }

    public static boolean ok(int l, int r, int[] counts) {
        int max = Math.max(Math.max(Math.max(counts[0],counts[1]),counts[2]),counts[3]);
        int caps = 4 * max - counts[0] - counts[1] - counts[2] - counts[3];
        return r - l >= caps;
    }

    public static void main(String[] args) {
        System.out.println(balancedString("WQWRQQQW"));
    }
}
